{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Island Perimeter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: islandPerimeter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #岛屿的周长"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <code>row x col</code> 的二维网格地图 <code>grid</code> ，其中：<code>grid[i][j] = 1</code> 表示陆地， <code>grid[i][j] = 0</code> 表示水域。</p>\n",
    "\n",
    "<p>网格中的格子 <strong>水平和垂直</strong> 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。</p>\n",
    "\n",
    "<p>岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/12/island.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>它的周长是上面图片中的 16 个黄色的边</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,0]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>row == grid.length</code></li>\n",
    "\t<li><code>col == grid[i].length</code></li>\n",
    "\t<li><code>1 <= row, col <= 100</code></li>\n",
    "\t<li><code>grid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [island-perimeter](https://leetcode.cn/problems/island-perimeter/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [island-perimeter](https://leetcode.cn/problems/island-perimeter/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]', '[[1]]', '[[1,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not grid:\n",
    "            return 0\n",
    "        n=len(grid[0])\n",
    "        m=len(grid)\n",
    "        conn=0\n",
    "        area=0\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y]==1:\n",
    "                    area+=1\n",
    "                    if y>0 and grid[x][y-1]==1:\n",
    "                        conn+=1\n",
    "                    if y<n-1 and grid[x][y+1]==1:\n",
    "                        conn+=1\n",
    "                    if x>0 and grid[x-1][y]==1:\n",
    "                        conn+=1\n",
    "                    if x<m-1 and grid[x+1][y]==1:\n",
    "                        conn+=1\n",
    "        return area*4-conn "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nrow = len(grid)\n",
    "        ncol = len(grid[0])\n",
    "        \n",
    "        mark = [[0 for ii in range(ncol)] for jj in range(nrow)]\n",
    "        \n",
    "        for ii in range(nrow):\n",
    "            for jj in range(ncol):\n",
    "                if grid[ii][jj] == 1:\n",
    "                    tmp = 1\n",
    "                    if ii + 1 <= nrow-1 and grid[ii+1][jj] == 1: tmp += 1\n",
    "                    if ii - 1 >= 0 and grid[ii-1][jj] == 1: tmp += 1\n",
    "                    if jj + 1 <= ncol-1 and grid[ii][jj+1] == 1: tmp += 1\n",
    "                    if jj - 1 >= 0 and grid[ii][jj-1] == 1: tmp += 1\n",
    "                    mark[ii][jj] = tmp\n",
    "        print(mark)\n",
    "        ans = 0\n",
    "        for ii in range(nrow):\n",
    "            for jj in range(ncol):\n",
    "                if mark[ii][jj] == 2: \n",
    "                    ans += 3\n",
    "                elif mark[ii][jj] == 3:\n",
    "                    ans += 2\n",
    "                elif mark[ii][jj] == 1:\n",
    "                    ans += 4\n",
    "                elif mark[ii][jj] == 4:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        \n",
    "        count1,count2=0,0\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    count1+=1\n",
    "                    if i>0 and grid[i-1][j]==1:\n",
    "                        count2+=1\n",
    "                    if j>0 and grid[i][j-1]==1:\n",
    "                        count2+=1                \n",
    "                    if i<m-1 and grid[i+1][j]==1:\n",
    "                        count2+=1\n",
    "                    if j<n-1 and grid[i][j+1]==1:\n",
    "                        count2+=1\n",
    "                    \n",
    "        return count1*4-count2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(grid)\n",
    "        width = len(grid[0])\n",
    "        index_list = []\n",
    "        count = 0\n",
    "        for i in range(length):\n",
    "            for j in range(width):\n",
    "                if grid[i][j] == 1:\n",
    "                    count += 4\n",
    "                    index = i * width + j\n",
    "                    if j > 0 and index - 1 in index_list:\n",
    "                        count -= 2\n",
    "                    if i > 0 and index - width in index_list:\n",
    "                        count -= 2\n",
    "                    index_list.append(index)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(grid)\n",
    "        width = len(grid[0])\n",
    "        index_list = set()\n",
    "        count = 0\n",
    "        for i in range(length):\n",
    "            for j in range(width):\n",
    "                if grid[i][j] == 1:\n",
    "                    count += 4\n",
    "                    index = i * width + j\n",
    "                    if j > 0 and index - 1 in index_list:\n",
    "                        count -= 2\n",
    "                    if index - width in index_list:\n",
    "                        count -= 2\n",
    "                    index_list.add(index)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: 'List[List[int]]') -> 'int':\n",
    "        res=0\n",
    "        j=0\n",
    "        a=[]\n",
    "        for l in grid:\n",
    "            for i in range(len(l)):\n",
    "                if l[i]==1:\n",
    "                    res+=4              \n",
    "                    a.append([j,i])\n",
    "                    if [j,i-1] in a:\n",
    "                        res-=2\n",
    "                    if [j-1,i] in a:\n",
    "                        res-=2\n",
    "            j+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        row = len(grid)\n",
    "        column = len(grid[0])\n",
    "        perimeter = 0\n",
    "        for i in range(row):\n",
    "            for j in range(column):\n",
    "                if grid[i][j] == 1:\n",
    "                    if i == 0: \n",
    "                        perimeter += 1\n",
    "                    else:\n",
    "                        if grid[i - 1][j] != 1:\n",
    "                            perimeter += 1\n",
    "                    if i == row - 1: \n",
    "                        perimeter += 1\n",
    "                    else:\n",
    "                        if grid[i + 1][j] != 1:\n",
    "                            perimeter += 1\n",
    "\n",
    "                    if j == 0:  \n",
    "                        perimeter += 1\n",
    "                    else:\n",
    "                        if grid[i][j - 1] != 1:\n",
    "                            perimeter += 1\n",
    "\n",
    "                    if j == column - 1: \n",
    "                        perimeter += 1\n",
    "                    else:\n",
    "                        if grid[i][j + 1] != 1:\n",
    "                            perimeter += 1\n",
    "        return perimeter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tg=[]\n",
    "\tdef findFirstLand(self):\n",
    "\t\theight=len(self.g)\n",
    "\t\twidth=len(self.g[0])\n",
    "\t\tfor i in range(height):\n",
    "\t\t\tfor j in range(width):\n",
    "\t\t\t\tif self.g[i][j]==1:\n",
    "\t\t\t\t\treturn [i,j]\n",
    "\tdef islandPerimeter(self, grid):\n",
    "\t\tself.g=grid\n",
    "\t\theight=len(self.g)\n",
    "\t\twidth=len(self.g[0])\n",
    "\t\tstack=[]\n",
    "\t\tcount=0\n",
    "\t\tstack.append(self.findFirstLand())\n",
    "\t\tfor t in stack:\n",
    "\t\t\tx=t[1]\n",
    "\t\t\ty=t[0]\n",
    "\t\t\tif grid[y][x]!=3:\n",
    "\t\t\t\tgrid[y][x]=3\n",
    "\t\t\t\tX=x\n",
    "\t\t\t\tY=y-1\n",
    "\t\t\t\tif Y>=0:\n",
    "\t\t\t\t\tif grid[Y][X]==0:\n",
    "\t\t\t\t\t\tcount+=1\n",
    "\t\t\t\t\telif grid[Y][X]==1:\n",
    "\t\t\t\t\t\tstack.append([Y,X])\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcount+=1\n",
    "\t\t\t\tX=x\n",
    "\t\t\t\tY=y+1\n",
    "\t\t\t\tif Y<height:\n",
    "\t\t\t\t\tif grid[Y][X]==0:\n",
    "\t\t\t\t\t\tcount+=1\n",
    "\t\t\t\t\telif grid[Y][X]==1:\n",
    "\t\t\t\t\t\tstack.append([Y,X])\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcount+=1\n",
    "\t\t\t\tX=x-1\n",
    "\t\t\t\tY=y\n",
    "\t\t\t\tif X>=0:\n",
    "\t\t\t\t\tif grid[Y][X]==0:\n",
    "\t\t\t\t\t\tcount+=1\n",
    "\t\t\t\t\telif grid[Y][X]==1:\n",
    "\t\t\t\t\t\tstack.append([Y,X])\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcount+=1\n",
    "\t\t\t\tX=x+1\n",
    "\t\t\t\tY=y\n",
    "\t\t\t\tif X<width:\n",
    "\t\t\t\t\tif grid[Y][X]==0:\n",
    "\t\t\t\t\t\tcount+=1\n",
    "\t\t\t\t\telif grid[Y][X]==1:\n",
    "\t\t\t\t\t\tstack.append([Y,X])\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcount+=1\n",
    "\t\treturn count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        if len(grid)==0 or len(grid[0])==0:\n",
    "            return res\n",
    "        for i in range(len(grid)):\n",
    "            res += sum(grid[i])*4\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==1 and i>0 and grid[i-1][j]==1:\n",
    "                    res -=2\n",
    "                if grid[i][j]==1 and j>0 and grid[i][j-1]==1:\n",
    "                    res -=2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        length = len(grid)\n",
    "        width = len(grid[0])\n",
    "        all_length=0\n",
    "        for i in range(length):\n",
    "            for j in range(width):\n",
    "                if grid[i][j]==1:\n",
    "                    if i==0 or grid[i-1][j]==0:\n",
    "                        all_length+=1\n",
    "                    if j==0 or grid[i][j-1]==0:\n",
    "                        all_length+=1\n",
    "        return all_length*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        c=0\n",
    "        l=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    c+=1\n",
    "                    if j+1<n and grid[i][j+1]==1:\n",
    "                        l+=1\n",
    "                    if i+1<m and grid[i+1][j]==1:\n",
    "                        l+=1\n",
    "        return 4*c-2*l\n",
    "        '''\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        c = 0\n",
    "        l = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    c += 1\n",
    "                    if j < m - 1 and grid[i][j + 1] == 1:\n",
    "                        l += 1\n",
    "                    if i < n - 1 and grid[i + 1][j] == 1:\n",
    "                        l += 1\n",
    "                    \n",
    "        return 4 * c - 2 * l\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid)==0:\n",
    "            return 0\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    res += 4\n",
    "                    if i>0 and grid[i-1][j]==1:\n",
    "                        res -= 1\n",
    "                    if i<len(grid)-1 and grid[i+1][j]==1:\n",
    "                        res -= 1\n",
    "                    if j>0 and grid[i][j-1]==1:\n",
    "                        res -= 1\n",
    "                    if j<len(grid[0])-1 and grid[i][j+1]==1:\n",
    "                        res -= 1\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        h = len(grid)\n",
    "        w = len(grid[0]) if h else 0\n",
    "        ans = 0\n",
    "        for x in range(h):\n",
    "            for y in range(w):\n",
    "                if grid[x][y] == 1:\n",
    "                    ans += 4\n",
    "                    # 因为x+1还在后面，所以不需要考虑，即只需要考虑左边和上边\n",
    "                    if x > 0 and grid[x-1][y]:\n",
    "                        # 为什么要减去2，因为两个边重合了都不计算了\n",
    "                        ans -= 2\n",
    "                    if y > 0 and grid[x][y-1]:\n",
    "                        ans -= 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        for i in range(len(grid)):\n",
    "            grid[i] = [0] +grid[i] +[0]\n",
    "        grid.insert(0,[0 for _ in range(len(grid[0]))])\n",
    "        grid.append([0 for _ in range(len(grid[0]))])\n",
    "        length = 0\n",
    "        for i in range(1,len(grid)-1):\n",
    "            for j in range(1,len(grid[0])-1):\n",
    "                if grid[i][j] ==1:\n",
    "                    l = 4\n",
    "                    if grid[i-1][j] == 1:\n",
    "                        l -= 1\n",
    "                    if grid[i][j-1] == 1:\n",
    "                        l-=1\n",
    "                    if grid[i+1][j] ==1:\n",
    "                        l-=1\n",
    "                    if grid[i][j+1] ==1:\n",
    "                        l -= 1\n",
    "                    length += l\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        dic = {}\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if grid[i][j] == 1:\n",
    "                    dic[(i, j)] = 4\n",
    "                    if (i-1, j) in dic:\n",
    "                        dic[(i, j)] -= 1\n",
    "                        dic[(i-1, j)] -= 1\n",
    "                    if (i, j-1) in dic:\n",
    "                        dic[(i, j)] -= 1\n",
    "                        dic[(i, j-1)] -= 1\n",
    "        return sum(dic.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        h = len(grid)\n",
    "        w = len(grid[0])\n",
    "        ans =0\n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if grid[i][j]==1:\n",
    "                    cnt = 0\n",
    "                    if j>=1 and grid[i][j-1]==1:\n",
    "                        cnt = cnt\n",
    "                    else:\n",
    "                        cnt +=1\n",
    "\n",
    "          \n",
    "                    if j<w-1 and grid[i][j+1]==1:\n",
    "                        cnt = cnt\n",
    "                    else:\n",
    "                        cnt +=1\n",
    "      \n",
    "                    if i>=1 and grid[i-1][j]==1:\n",
    "                        cnt = cnt\n",
    "                    else:\n",
    "                        cnt +=1\n",
    "\n",
    "                    if i<h-1 and grid[i+1][j]==1:\n",
    "                        cnt = cnt\n",
    "                    else:\n",
    "                        cnt +=1\n",
    "\n",
    "                    ans +=cnt\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        num, div, i, j = 0,0,0,0\n",
    "        island = lambda i,j: True if i in range(row) and j in range(col) else False\n",
    "        while island(i, j):\n",
    "            if grid[i][j] == 1:\n",
    "                num += 1\n",
    "                if island(i-1, j) and grid[i-1][j] == 1:\n",
    "                    div += 1\n",
    "                if island(i, j-1) and grid[i][j-1] == 1:\n",
    "                    div += 1\n",
    "                if island(i+1, j) and grid[i+1][j] == 1:\n",
    "                    div += 1\n",
    "                if island(i, j+1) and grid[i][j+1] == 1:\n",
    "                    div += 1\n",
    "            if j == col-1:\n",
    "                j = 0\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return num*4-div"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        adj = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "\n",
    "        def adjLand(grid, i, j):\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            ans = 0\n",
    "            for v in adj:\n",
    "                x, y = i + v[0], j + v[1]\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    if grid[x][y] == 1:\n",
    "                        ans += 1\n",
    "            return ans        \n",
    "\n",
    "        res = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    res += 4 - adjLand(grid, i, j)\n",
    "        return res\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        p = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                if (i != 0 and grid[i-1][j] == 0) or i == 0:\n",
    "                    p += 1\n",
    "                if (i != row-1 and grid[i+1][j] == 0) or i == row-1:\n",
    "                    p += 1\n",
    "                if (j != 0 and grid[i][j-1] == 0) or j == 0:\n",
    "                    p += 1\n",
    "                if (j != col-1 and grid[i][j+1] == 0) or j == col-1:\n",
    "                    p += 1\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        lrow = 0\n",
    "        lline = 0\n",
    "\n",
    "        x = len(grid[0])\n",
    "        y = len(grid)\n",
    "\n",
    "        \n",
    "\n",
    "        grid_y = [[] for _ in range(x)]\n",
    "\n",
    "        for row in grid:\n",
    "            rcount = self.counts(row)\n",
    "            lrow += rcount*2\n",
    "\n",
    "            for i in range(x):\n",
    "                grid_y[i].append(row[i])\n",
    "        for line in grid_y:\n",
    "            lcount = self.counts(line)\n",
    "            lline += lcount*2\n",
    "        return lrow+lline\n",
    "        \n",
    "         \n",
    "                 \n",
    "\n",
    "    def counts(self, nums):\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        count = 0\n",
    "        while i < n:\n",
    "            if nums[i]==0:\n",
    "                i+=1\n",
    "            else:\n",
    "                count += 1\n",
    "                j = 1\n",
    "                while j < n-i:\n",
    "                    if nums[i+j] == 1:\n",
    "                        j+=1\n",
    "                    else:\n",
    "                        i = i+j\n",
    "                        break\n",
    "                else:\n",
    "                    i = i+j\n",
    "        return count \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]])->int:\n",
    "        m, n = len(grid), len(grid[0])  #m行n列\n",
    "        #加两行\n",
    "        grid.insert(0, [0 for _ in range(n)])\n",
    "        grid.append([0 for _ in range(n)])\n",
    "        #加两列\n",
    "        for i in range(m+2):\n",
    "            grid[i] = [0] + grid[i] + [0]\n",
    "        s = 0\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if grid[i][j] == 1:\n",
    "                    if grid[i+1][j] == 0:\n",
    "                        s += 1\n",
    "                    if grid[i-1][j] == 0:\n",
    "                        s += 1\n",
    "                    if grid[i][j+1] == 0:\n",
    "                        s += 1\n",
    "                    if grid[i][j-1] == 0:\n",
    "                        s += 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            grid[i].insert(0,0)\n",
    "            grid[i].append(0)\n",
    "\n",
    "        grid.insert(0,[0]*(n+2))\n",
    "        grid.append([0]*(n+2))\n",
    "\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if grid[i][j]:\n",
    "                    if not grid[i+1][j]:\n",
    "                        count+=1\n",
    "                    if not grid[i-1][j]:\n",
    "                        count+=1\n",
    "                    if not grid[i][j+1]:\n",
    "                        count+=1\n",
    "                    if not grid[i][j-1]:\n",
    "                        count+=1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return count\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        count = 0\n",
    "        print(row,col)\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    if i == 0:\n",
    "                        count += 1\n",
    "                    elif grid[i-1][j] == 0:\n",
    "                        count += 1\n",
    "                    \n",
    "                    if i == row - 1:\n",
    "                        count += 1\n",
    "                    elif grid[i + 1][j] == 0:\n",
    "                        count += 1\n",
    "                    \n",
    "                    if j == 0:\n",
    "                        count += 1\n",
    "                    elif grid[i][j - 1] == 0:\n",
    "                        count += 1\n",
    "                    \n",
    "                    if j == col -1:\n",
    "                        count += 1\n",
    "                    elif grid[i][j + 1] == 0:\n",
    "                        count += 1\n",
    "                    \n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if not grid[i][j]:\n",
    "                    continue\n",
    "                temp = 0\n",
    "                if not i:\n",
    "                    temp += 1\n",
    "                else:\n",
    "                    if not grid[i-1][j]:\n",
    "                        temp += 1\n",
    "                \n",
    "                if i == len(grid)-1:\n",
    "                    temp += 1\n",
    "                else:\n",
    "                    if not grid[i+1][j]:\n",
    "                        temp += 1\n",
    "                if not j:\n",
    "                    temp += 1\n",
    "                else:\n",
    "                    if not grid[i][j-1]:\n",
    "                        temp += 1\n",
    "                if j == len(grid[0])-1:\n",
    "                    temp += 1\n",
    "                else:\n",
    "                    if not grid[i][j+1]:\n",
    "                        temp += 1\n",
    "                res += temp\n",
    "                print(temp)\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        island = set()\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]:\n",
    "                    island.add((i, j))\n",
    "                    ans += 4 - (((i - 1, j) in island) + ((i, j - 1) in island)) * 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        tmpset = set()\n",
    "        ln = 0\n",
    "        cown = len(grid)\n",
    "        rown = len(grid[0])\n",
    "        for cow in range(cown):\n",
    "            for row in range(rown):\n",
    "                if grid[cow][row] == 1:\n",
    "                    if (cow - 1, row) not in tmpset:\n",
    "                        ln += 1\n",
    "                    else:\n",
    "                        ln -= 1\n",
    "                    if (cow + 1, row) not in tmpset:\n",
    "                        ln += 1\n",
    "                    else:\n",
    "                        ln -= 1\n",
    "                    if (cow, row - 1) not in tmpset:\n",
    "                        ln += 1\n",
    "                    else:\n",
    "                        ln -= 1\n",
    "                    if (cow, row + 1) not in tmpset:\n",
    "                        ln += 1\n",
    "                    else:\n",
    "                        ln -= 1\n",
    "                    tmpset.add((cow, row))\n",
    "        return ln"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def searching_Island_Problems(grid,searchingThisSymbol,allDir):\n",
    "    def possibleNeighbor(pos):\n",
    "        output=[]\n",
    "        x=pos[0]\n",
    "        y=pos[1]\n",
    "        for t in allDir:\n",
    "            x,y=pos[0]+t[0],pos[1]+t[1]\n",
    "            if 0<=x<N and 0<=y<M:\n",
    "                if grid[x][y]==searchingThisSymbol:\n",
    "                    output.append((x,y))\n",
    "        return output\n",
    "\n",
    "\n",
    "\n",
    "    res=[]\n",
    "    visited=set()\n",
    "    N,M=len(grid),len(grid[0])\n",
    "    for i in range(N):\n",
    "        for j in range(M):\n",
    "            if (i,j) not in visited:\n",
    "                visited.add((i,j))\n",
    "                if grid[i][j]==searchingThisSymbol:\n",
    "                    frontier=[(i,j)]\n",
    "                    cnt=1\n",
    "                    zc=0\n",
    "                    while frontier:\n",
    "                        pos=frontier.pop()\n",
    "                        posNew=possibleNeighbor(pos)\n",
    "                        if pos not in visited:\n",
    "                            visited.add(pos)\n",
    "                            cnt+=1\n",
    "                            if pos!=(i,j):\n",
    "                                zc+=len(allDir)-len(posNew)\n",
    "                        if pos==(i,j):\n",
    "                            zc+=len(allDir)-len(posNew)\n",
    "                        for new_pos in posNew:\n",
    "                            if new_pos not in visited:\n",
    "                                frontier.append(new_pos)\n",
    "                    res.append((cnt,zc))\n",
    "    return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        searchingThisSymbol=1#要找的那种花色\n",
    "        allDir=[(0,1),(0,-1),(1,0),(-1,0)]#[(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,-1),(-1,1)]\n",
    "        all_island_with_their_respective_Area_AND_Perimeter=searching_Island_Problems(grid,searchingThisSymbol,allDir)\n",
    "        numIslands=len(all_island_with_their_respective_Area_AND_Perimeter)\n",
    "        if all_island_with_their_respective_Area_AND_Perimeter:\n",
    "            maxIslandArea=max(t[0] for t in all_island_with_their_respective_Area_AND_Perimeter)\n",
    "            maxZhouChang=max(t[1] for t in all_island_with_their_respective_Area_AND_Perimeter)\n",
    "        else:\n",
    "            maxIslandArea=0\n",
    "            maxZhouChang=0\n",
    "        return maxZhouChang"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]:\n",
    "                    return self.DFS(grid,i,j)\n",
    "        \n",
    "    \n",
    "    def DFS(self,grid,r,c):\n",
    "\n",
    "        if not ( r >= 0 and r < len(grid) and c >= 0 and c < len(grid[0])):\n",
    "            return 1\n",
    "        if grid[r][c] == 0:\n",
    "            return 1\n",
    "        if grid[r][c] != 1:\n",
    "            return 0\n",
    "        grid[r][c] = 2\n",
    "\n",
    "        return self.DFS(grid,r+1,c) + self.DFS(grid,r-1,c) + \\\n",
    "         self.DFS(grid,r,c+1) + self.DFS(grid,r,c-1)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        def isArea(grid, r, c):\n",
    "            return r>=0 and r<len(grid) and c>=0 and c<len(grid[0])\n",
    "        \n",
    "        def dfs(grid, r, c):\n",
    "            # 碰到边界，返回一条边\n",
    "            if not isArea(grid, r, c):\n",
    "                return 1\n",
    "            # 碰到海洋，返回一条边\n",
    "            if grid[r][c] == 0:\n",
    "                return 1\n",
    "            # 相邻的陆地没有边\n",
    "            if grid[r][c] != 1:\n",
    "                return 0\n",
    "            grid[r][c] = 2\n",
    "\n",
    "            return dfs(grid, r-1, c) + dfs(grid, r+1, c) + dfs(grid, r, c-1) + dfs(grid, r, c+1)\n",
    "        \n",
    "        for r in range(len(grid)):\n",
    "            for c in range(len(grid[0])):\n",
    "                if grid[r][c] == 1:\n",
    "                    return dfs(grid, r, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(grid, i, j):\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == 0:\n",
    "                return 1\n",
    "            if grid[i][j] == 2:\n",
    "                return 0\n",
    "            \n",
    "            grid[i][j] = 2\n",
    "            perimeter = 0\n",
    "            perimeter += dfs(grid, i-1, j)\n",
    "            perimeter += dfs(grid, i+1, j)\n",
    "            perimeter += dfs(grid, i, j-1)\n",
    "            perimeter += dfs(grid, i, j+1)\n",
    "            return perimeter\n",
    "            \n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans += dfs(grid, i, j)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        # def dfs(grid, i, j):\n",
    "        #     m, n = len(grid), len(grid[0])\n",
    "        #     if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == 0:\n",
    "        #         return 1\n",
    "        #     if grid[i][j] == 2:\n",
    "        #         return 0\n",
    "\n",
    "\n",
    "        #     grid[i][j] = 2\n",
    "        #     perimeter = 0\n",
    "        #     perimeter += dfs(grid, i-1, j)\n",
    "        #     perimeter += dfs(grid, i+1, j)\n",
    "        #     perimeter += dfs(grid, i, j-1)\n",
    "        #     perimeter += dfs(grid, i, j+1)\n",
    "\n",
    "        #     return perimeter\n",
    "        \n",
    "        # perimeter = 0\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if grid[i][j] == 1:\n",
    "        #             perimeter += dfs(grid, i, j)\n",
    "        # return perimeter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        perimeter = 0\n",
    "\n",
    "        def dfs(x, y, m, n):\n",
    "            if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                return 1\n",
    "            if grid[x][y] == 0:\n",
    "                return 1\n",
    "            if grid[x][y] == 2:\n",
    "                return 0\n",
    "            grid[x][y] = 2\n",
    "            return dfs(x + 1, y, m, n) + dfs(x - 1, y, m, n) + dfs(x, y + 1, m, n) + dfs(x, y - 1, m, n)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    perimeter += dfs(i, j, m, n)\n",
    "\n",
    "        return perimeter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,grid,i,j):\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])               \n",
    "        if i<0 or i>= n or j<0 or j>=m:\n",
    "            return 1\n",
    "        if grid[i][j] == 2:\n",
    "            return 0\n",
    "        if grid[i][j] == 0:\n",
    "            return 1\n",
    "        grid[i][j] = 2\n",
    "        res = 0 \n",
    "        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "            x=i+dx\n",
    "            y=j+dy\n",
    "            res = res + self.dfs(grid,x,y)\n",
    "        return res\n",
    "        \n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])  \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans = ans+self.dfs(grid,i,j)\n",
    "        return ans\n",
    "\n",
    "\n",
    "                            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def  __init__(self):\n",
    "        self.position=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "    def dfs(self,grid,row,col,m,n):\n",
    "        grid[row][col]=2\n",
    "        number=0\n",
    "        for current in self.position:\n",
    "            newRow=row+current[0]\n",
    "            newCol=col+current[1]\n",
    "            if (newCol>=n or newCol<0 or newRow<0 or newRow>=m) or grid[newRow][newCol]==0:\n",
    "                number+=1\n",
    "            elif grid[newRow][newCol]==1:\n",
    "                number+=self.dfs(grid,newRow,newCol,m,n)\n",
    "\n",
    "        return number\n",
    "\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    output=self.dfs(grid,i,j,m,n)\n",
    "        \n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        def inArea(grid, row, col):\n",
    "            return 0<=row and row<len(grid) and 0<=col and col<len(grid[0])\n",
    "        \n",
    "        def dfs(grid, row, col):\n",
    "            if not inArea(grid, row, col):\n",
    "                return 1\n",
    "            if grid[row][col] == 2:\n",
    "                return 0\n",
    "            \n",
    "            if grid[row][col] == 0:\n",
    "                return 1\n",
    "            grid[row][col] = 2\n",
    "            \n",
    "            return dfs(grid,row-1,col)+dfs(grid,row+1,col)+dfs(grid,row,col-1)+dfs(grid,row,col+1)\n",
    "            \n",
    "            \n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans += dfs(grid, i, j)\n",
    "                    print(i,j,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        def inarea(grid,r,c):\n",
    "            return 0<=r and r<len(grid) and 0<=c and c<len(grid[0])\n",
    "        def dfs(grid,r,c):\n",
    "            if not inarea(grid,r,c):\n",
    "                return 1\n",
    "            if grid[r][c]==0:\n",
    "                return 1\n",
    "            if grid[r][c]==2:\n",
    "                return 0\n",
    "            grid[r][c]=2\n",
    "            return dfs(grid,r+1,c)+dfs(grid,r-1,c)+dfs(grid,r,c+1)+dfs(grid,r,c-1)\n",
    "        res=0\n",
    "        for r in range(len(grid)):\n",
    "            for c in range(len(grid[0])):\n",
    "                if grid[r][c]==1:\n",
    "                    res=dfs(grid,r,c)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        def dfs(x,y):\n",
    "            if x<0 or x>=m or y<0 or y>=n or grid[x][y]==0 :\n",
    "                return 0 \n",
    "            if grid[x][y]==2:\n",
    "                return -1\n",
    "            grid[x][y]=2\n",
    "            res=4\n",
    "            for i,j in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "                t_res=dfs(x+i,y+j)\n",
    "                if t_res!=0:\n",
    "                    res+=t_res\n",
    "            print(x,y,res)\n",
    "            return res-1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    return dfs(i,j)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        # 先pad\n",
    "        for r in range(len(grid)):\n",
    "            grid[r] = [0] + grid[r] + [0]\n",
    "        grid = [[0] * len(grid[0])] + grid + [[0] * len(grid[0])]\n",
    "\n",
    "        self.res = 0\n",
    "\n",
    "        def dfs(r, c):\n",
    "            if grid[r][c] == 0:\n",
    "                self.res += 1\n",
    "                return \n",
    "            elif grid[r][c] == 1:\n",
    "                grid[r][c] = None\n",
    "                dfs(r+1, c)\n",
    "                dfs(r-1, c)\n",
    "                dfs(r, c+1)\n",
    "                dfs(r, c-1)\n",
    "\n",
    "        for r in range(1, len(grid) - 1):\n",
    "            for c in range(1, len(grid[0]) - 1):\n",
    "                if grid[r][c] == 1:\n",
    "                    dfs(r, c)\n",
    "                    return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        result=0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        direct=[(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        # dfs\n",
    "        def dfs(grid,x,y):\n",
    "            nonlocal m,n,direct\n",
    "            if x<0 or y<0 or x>=m or y>=n or grid[x][y]==0:\n",
    "                return 1\n",
    "            if grid[x][y]==2:\n",
    "                return 0\n",
    "            grid[x][y]=2\n",
    "            result=0\n",
    "            for i in range(4):\n",
    "                nx=x+direct[i][0]\n",
    "                ny=y+direct[i][1]\n",
    "                result+=dfs(grid,nx,ny)\n",
    "            return result\n",
    "            \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    return dfs(grid,i,j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    #深搜可能出现问题\n",
    "    def __init__(self):\n",
    "        self.directions = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        self.num = 0\n",
    "        self.adj = 0#主要还是怕没检测出来准确的相邻数量\n",
    "\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        visited = [[0]*(len(grid[0])) for _ in range(len(grid))]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if not visited[i][j] and grid[i][j]:\n",
    "                    visited[i][j] = 1\n",
    "                    self.DFS(grid, visited, i,j)\n",
    "        return (self.num + 1)*4 - 2*self.adj\n",
    "        \n",
    "    def DFS(self,grid, visited, x, y):\n",
    "        for i,j in self.directions:\n",
    "            next_x = x + i\n",
    "            next_y = y + j\n",
    "            if next_x < 0 or next_y < 0 or next_x > len(grid)-1 or next_y > len(grid[0]) -1 :\n",
    "                continue\n",
    "            if not visited[next_x][next_y] and grid[next_x][next_y]:\n",
    "                self.num += 1\n",
    "                visited[next_x][next_y] = 1\n",
    "                self.dectect(grid,visited,next_x,next_y)\n",
    "                self.DFS(grid,visited, next_x, next_y)\n",
    "        return\n",
    "\n",
    "    def dectect(self,grid,visited, x,y):\n",
    "        for i,j in self.directions:\n",
    "            next_x = x + i\n",
    "            next_y = y + j \n",
    "            if next_x < 0 or next_y < 0 or next_x > len(grid)-1 or next_y > len(grid[0]) -1 :\n",
    "                continue\n",
    "            if visited[next_x][next_y]:\n",
    "                self.adj += 1               \n",
    "    # def BFS(self,grid, visited, x, y):\n",
    "    #     queue = deque()\n",
    "    #     queue.append((x,y))\n",
    "    #     while queue:\n",
    "    #         cur_x,cur_y = queue.popleft()\n",
    "\n",
    "\n",
    "    #         for i,j in self.directions:\n",
    "    #             next_x = cur_x + i\n",
    "    #             next_y = cur_y + j\n",
    "    #             if next_x < 0 or next_y < 0 or next_x > len(grid)-1 or next_y > len(grid[0]) -1 :\n",
    "    #                 continue\n",
    "    #             if not visited[next_x][next_y] and grid[next_x][next_y]:\n",
    "    #                 self.adj_num += 1\n",
    "    #                 visited[next_x][next_y] = 1\n",
    "    #                 self.DFS(grid,visited, next_x, next_y)\n",
    "    #     return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(nums, i, j):\n",
    "            if not (0 <= i < m) or not (0 <= j< n):\n",
    "                return 0\n",
    "            \n",
    "            if nums[i][j] == 0:\n",
    "                return 0\n",
    "            elif nums[i][j] == 2:\n",
    "                return 0\n",
    "            else:\n",
    "                cur = 0\n",
    "                nums[i][j] = 2\n",
    "                for p, q in [(0, 1), (0, -1), (1, 0), (-1, 0)]:                  \n",
    "                    if not (0 <= i + p < m) or not (0 <= j + q< n):\n",
    "                        cur += 1\n",
    "                    elif nums[i + p][j + q] == 0:\n",
    "                        cur += 1\n",
    "                    elif nums[i + p][j + q] == 1:\n",
    "                        cur += dfs(nums, i + p, j + q) \n",
    "                    \n",
    "                return cur\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    return dfs(grid, i, j)\n",
    "                \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        n_row, n_col = len(grid), len(grid[0])\n",
    "        def dfs(i, j):\n",
    "            if i >= n_row or j >= n_col or i < 0 or j < 0:\n",
    "                return 1\n",
    "            if grid[i][j] == 0:\n",
    "                return 1\n",
    "            elif grid[i][j] == 2:\n",
    "                return 0\n",
    "            grid[i][j] = 2\n",
    "            return dfs(i, j-1) + dfs(i, j+1) + dfs(i-1,j) + dfs(i+1, j)\n",
    "        cur_max = 0\n",
    "        for i in range(n_row):\n",
    "            for j in range(n_col):\n",
    "                if grid[i][j] == 1:\n",
    "                    cur_max = max(cur_max, dfs(i, j))\n",
    "        return cur_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans += self.dfs(grid, row, col, i, j)\n",
    "                    \n",
    "        return ans\n",
    "\n",
    "    \n",
    "    def dfs(self, grid, row, col, x, y):\n",
    "        if grid[x][y] == 0:\n",
    "            return 0\n",
    "        grid[x][y] = 2\n",
    "        cnt_neighbour = 0\n",
    "        ttl_c = 4\n",
    "        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:\n",
    "            xhat, yhat = x + dx, y + dy\n",
    "            if -1 < xhat < row and -1 < yhat < col and grid[xhat][yhat] >0:\n",
    "                cnt_neighbour += 1\n",
    "            if -1 < xhat < row and -1 < yhat < col and grid[xhat][yhat] == 1:\n",
    "                c = self.dfs(grid, row, col, xhat, yhat)\n",
    "                ttl_c += c\n",
    "            \n",
    "        ttl_c -= cnt_neighbour\n",
    "        return ttl_c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "\n",
    "        r_edges = [[0] * c for _ in range(r+1)]\n",
    "        c_edges = [[0] * (c+1) for _ in range(r)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            nonlocal grid\n",
    "            if i < 0 or i >= r or j < 0 or j >= c or grid[i][j] != 1:\n",
    "                return\n",
    "            grid[i][j] = 0\n",
    "            r_edges[i][j] = 1 - r_edges[i][j]\n",
    "            r_edges[i+1][j] = 1 - r_edges[i+1][j]\n",
    "            c_edges[i][j] = 1 - c_edges[i][j]\n",
    "            c_edges[i][j+1] = 1 - c_edges[i][j+1]\n",
    "            dfs(i-1,j)\n",
    "            dfs(i+1,j)\n",
    "            dfs(i,j-1)\n",
    "            dfs(i,j+1)\n",
    "\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i,j)\n",
    "        return sum(element for row in r_edges for element in row) + sum(element for row in c_edges for element in row)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        visited=[[0]*n for i in range(m)]\n",
    "        direc=[[1,0],[0,1],[-1,0],[0,-1]]\n",
    "        self.cur=0\n",
    "        self.cnt=0\n",
    "        self.ans=0\n",
    "        def dfs(i,j):\n",
    "            self.cur+=4\n",
    "            visited[i][j]=1\n",
    "            self.cnt+=1\n",
    "            # print(i,j)\n",
    "            for di,dj in direc:\n",
    "                if 0<=i+di<m and 0<=j+dj<n and grid[i+di][j+dj]:\n",
    "                    self.cur-=1\n",
    "                if 0<=i+di<m and 0<=j+dj<n and visited[i+di][j+dj]==0 and grid[i+di][j+dj]:\n",
    "                     \n",
    "                    \n",
    "                    # visited[i+di][j+dj]=1\n",
    "                    dfs(i+di,j+dj)\n",
    "                    # visited[i+di][j+dj]=0\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] and visited[i][j]==0:\n",
    "                    self.cur=0\n",
    "                    dfs(i,j)\n",
    "                    self.ans=max(self.ans,self.cur)\n",
    "        # print(self.cnt)\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "            \n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i, j):\n",
    "            # 遇到边界，海域都应该计算接壤边\n",
    "            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:\n",
    "                return 1\n",
    "            # 如果重复访问，则不计算\n",
    "            if grid[i][j] == -1:\n",
    "                return 0\n",
    "            \n",
    "            # 陆地格子要先进行标记， 设为 -1\n",
    "            grid[i][j] = -1\n",
    "            # 计算有效边（须计入周长的边）\n",
    "            total = 0\n",
    "            # 在当前陆地格子，往四个方位进行扩散搜索\n",
    "            for di, dj in directions:\n",
    "                ni = i + di\n",
    "                nj = j + dj\n",
    "                total += dfs(ni, nj)\n",
    "\n",
    "            return total\n",
    "\n",
    "        # 四个方位        \n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "\n",
    "        ans = 0\n",
    "        # 在网格上遍历，先找到第一块陆地格子，然后扩散\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans += dfs(i, j)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid) -> int:\n",
    "        if not grid and not grid[0]:\n",
    "            return 0\n",
    "        height, width = len(grid), len(grid[0])\n",
    "        visited = [[False for i in range(width)] for j in range(height)]\n",
    "        direct_x = [-1, 0, 1, 0]\n",
    "        direct_y = [0, -1, 0, 1]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            if x < 0 or y < 0 or x >= height or y >= width or visited[x][y] or grid[x][y] == 0:\n",
    "                return 0\n",
    "            res = 4\n",
    "            visited[x][y] = True\n",
    "            for i in range(4):\n",
    "                next_x, next_y = x + direct_x[i], y + direct_y[i]\n",
    "                if 0 <= next_x < height and 0 <= next_y < width and grid[next_x][next_y] == 1:\n",
    "                    res -= 1\n",
    "                    if not visited[next_x][next_y]:\n",
    "                        res += dfs(next_x, next_y)\n",
    "            return res\n",
    "\n",
    "        for i in range(height):\n",
    "            for j in range(width):\n",
    "                if grid[i][j] == 1:\n",
    "                    return dfs(i, j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "        dirs = [[0,1], [1,0], [0,-1], [-1,0]]\n",
    "        def dfs(cur_i, cur_j):\n",
    "            visited[cur_i][cur_j] = True\n",
    "            cur_peri = 4\n",
    "            for i, j in dirs:\n",
    "                next_i = cur_i + i\n",
    "                next_j = cur_j + j\n",
    "                if 0 <= next_i < len(grid) and 0 <= next_j < len(grid[0]) and grid[next_i][next_j]:\n",
    "                    cur_peri -= 1\n",
    "                    if not visited[next_i][next_j]:\n",
    "                        cur_peri += dfs(next_i, next_j)\n",
    "            return cur_peri\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    return dfs(i, j)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def islandPerimeter(self, grid: List[List[int]]) -> int:\n",
    "        # 四周有x个陆地，答案记录4-x个边长\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        vis = set()\n",
    "        def dfs(i, j):\n",
    "            if (i, j) in vis: return\n",
    "            vis.add((i, j))\n",
    "            cnt = 0\n",
    "            for ni, nj in (i+1, j), (i-1, j), (i, j+1), (i, j-1):\n",
    "                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:\n",
    "                    cnt += 1\n",
    "                    dfs(ni, nj)\n",
    "            nonlocal ans\n",
    "            ans += 4 - cnt\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j)\n",
    "                    return ans\n",
    "                    \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
